package com.datastructure.test.canfinish;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class CanFinish {

    public static void main(String[] args) {

    }

    public boolean canFinish (int numProject, ArrayList<ArrayList<Integer>> groups) {
        // write code here
        Set<Integer>[] G = new Set[numProject];
        for(int i = 0; i < numProject; ++i) {
            G[i] = new HashSet<>();
        }
        int[] d = new int[numProject];
        for(ArrayList<Integer> e : groups) {
            ++d[e.get(0)];
            G[e.get(1)].add(e.get(0));
        }
        ArrayList<Integer> ans = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < numProject; ++i) {
            if(0 == d[i]) {
                stack.push(i);
            }
        }
        while(!stack.isEmpty()) {
            int x = stack.pop();
            ans.add(x);
            for(int y : G[x]) {
                if(--d[y] == 0) {
                    stack.push(y);
                }
            }
        }
        return numProject == ans.size();
    }
}
